/*
	解法：获取第n个节点的值，第n个节点前插入节点，删除第n个结点
	为什么：用第0个结点检查算法是否写对
	时间复杂度：，空间复杂度：O(n)
 */

#include <iostream>

using namespace std;

struct ListNode
{
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(nullptr) {}		//初始化列表方式初始化构造函数
};

class MyLinkedList
{
private:
	ListNode* dummyHead; // 虚拟头节点
	int size;
	
public:
	MyLinkedList()
	{
		dummyHead = new ListNode(-1);
		size = 0;
	}
	
	~MyLinkedList()
	{
		ListNode* curr = dummyHead;
		while (curr != nullptr)
		{
			ListNode* next = curr->next;
			delete curr;
			curr = next;
		}
	}
	
	int get(int index)
	{
		if (index < 0 || index >= size)
		{
			return -1;
		}
		
		ListNode* curr = dummyHead->next;
		for (int i = 0; i < index; ++i)
		{
			curr = curr->next;
		}
		
		return curr->val;
	}
	
	void addAtHead(int val)
	{
		addAtIndex(0, val);
	}
	
	void addAtTail(int val)
	{
		addAtIndex(size, val);
	}
	
	void addAtIndex(int index, int val)
	{
		if (index < 0)
		{
			index = 0;		//如果 index < 0，把它调整为 0（仍然插入链表头）
		}
		if (index > size)
		{
			return;
		}
		
		ListNode* prev = dummyHead;
		for (int i = 0; i < index; ++i)
		{
			prev = prev->next;      //找到第 index 个节点的前一个节点 prev
		}
		
		ListNode* newNode = new ListNode(val);
		newNode->next = prev->next;		//prev->next就是第index个节点的地址
		prev->next = newNode;
		
		++size;
	}
	
	void deleteAtIndex(int index)
	{
		if (index < 0 || index >= size)
		{
			return;
		}
		
		ListNode* prev = dummyHead;
		for (int i = 0; i < index; ++i)
		{
			prev = prev->next;      //找到第 index 个节点的前一个节点 prev
		}
		
		ListNode* toDelete = prev->next;		//prev->next就是要删除的第index个节点的地址
		prev->next = toDelete->next;
		delete toDelete;
		
		--size;
	}
	
	// 测试函数：打印链表
	void printList()
	{
		ListNode* curr = dummyHead->next;
		while (curr != nullptr)
		{
			cout << curr->val;
			if (curr->next != nullptr)
			{
				cout << " -> ";
			}
			curr = curr->next;
		}
		cout << endl;
	}
};

int main()
{
	MyLinkedList myLinkedList;
	
	myLinkedList.addAtHead(1);         // 链表：1
	myLinkedList.addAtTail(3);         // 链表：1 -> 3
	myLinkedList.addAtIndex(1, 2);     // 链表：1 -> 2 -> 3
	cout << "get(1) = " << myLinkedList.get(1) << endl;  // 输出 2
	
	myLinkedList.deleteAtIndex(1);     // 链表：1 -> 3
	cout << "get(1) = " << myLinkedList.get(1) << endl;  // 输出 3
	
	cout << "最终链表：" << endl;
	myLinkedList.printList();          // 输出链表结构
	
	return 0;
}



